跳到主要内容

LCR 101.分割等和子集

· 阅读需 3 分钟

1、题干​

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

 

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：nums 可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：nums 不可以分为和相等的两部分

 

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

 

注意：本题与主站 416 题相同： https://leetcode-cn.com/problems/partition-equal-subset-sum/

2、解题思路​

根据题意需要找到数组 nums 所有元素和的一半 target，可以这么做：遍历数组 nums，用哈希集合 set 记录所有元素和，若 nums 或 set 中存在 target，则返回 true。

注意 ：这个解法的关键在于必须限定 set 只能存储比 target 更小的元素和，否则大概率会超时。由于数组 nums 长度已经固定，而 set 被限制后其长度必然小于 target，因此总体时间复杂度为：O(n∗target)O(n*target)，计算量级最大约为 10610^6，超时的可能性不大。


3、代码​

var canPartition = function (nums) {
    const sum = nums.reduce((a, c) => a + c, 0);
    if (sum % 2) return false;

    const target = sum / 2, set = new Set();
    for (const n of nums) {
        if (n > target) continue;
        if (target === n || set.has(target - n)) return true;
        for (const s of [...set]) if (n + s < target) set.add(n + s);
        set.add(n);
    }

    return false;
};

4、复杂度​

  • 时间复杂度：O(n∗target)O(n*target)
  • 空间复杂度：O(target)O(target)

5、执行结果​

  • 执行用时: 112 ms
  • 内存消耗: 47.1 MB